class Solution {
public:
    // 1:1  2:2  3:4  4:8  5:16
/* 
 //公式计算
    // f(n) = 2^(n-1)
    int jumpFloorII(int number) {
        int fib[] = {0, 1, 2};
        if(number < 3)
            return fib[number];
   
        int retnum = pow(2, number-1);
        return retnum;
    }
 */
    
    // DP
    int jumpFloorII(int number) {
        int fib[] = {0, 1, 2};
        if(number < 3)
            return fib[number];
        vector<int> dp(number+1);
        int sum = 1;
        for(int i = 2; i <= number; ++i){
            dp[i] = sum+1;
            sum += dp[i];
        }
        return dp[number];
    }
};